﻿#define _CRT_SECURE_NO_WARNINGS 1
/**给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*/
//int maxLength(int* arr, int arrLen) {
//	// write code here
//	int res = 0;
//	int freq[100000] = { 0 };
//	int l = 0;
//	int r = -1;
//	while (l<arrLen)
//	{
//		if (r<arrLen - 1 && freq[arr[r + 1]] == 0)
//		{
//			freq[arr[++r]]++;
//		}
//		else
//		{
//			freq[arr[l++]]--;
//		}
//		res = fmax(res, r - l + 1);
//	}
//	return  res;
//}








/**有一个长度为len只包含小写字母‘a’-'z'的字符串x，现在想要一个特殊的子序列，这个子序列的长度为3*n（n为非负整数），子序列的第[1,n]个字母全部为‘a’，子序列的[n+1,2*n]个字母全部为‘b’，子序列的[2*n+1,3*n]个字母全部为‘c’，求最长的符合条件的独特子序列的长度是多少。

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param x string字符串
* @return int整型
*/
//int Maximumlength(char* x) {
//	// write code here
//	int len = strlen(x) - 1;
//	int l = 0;
//	int r = len - 1;
//	int a = 0;
//	int b = 0;
//	int c = 0;
//	int ml = 0;
//	for (int i = 0; i<len; i++)
//	{
//		if (x[i] == 'b')
//		{
//			b++;
//		}
//	}
//	while (l<r)
//	{
//		while (x[l] != 'a'&&l<r)
//		{
//			if (x[l] == 'b')
//			{
//				b--;
//			}
//			l++;
//		}
//		while (x[r] != 'c'&&r>l)
//		{
//			if (x[r] == 'b')
//			{
//				b--;
//			}
//			r--;
//		}
//		a++;
//		c++;
//		ml = fmax(ml, (fmin(a, fmin(b, c))) * 3);
//		l++;
//		r--;
//	}
//	return ml;
//}







/**字符串可以变为字符串B时返回true。
例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同返回true。
* 旋转字符串
* @param A string字符串
* @param B string字符串
* @return bool布尔型
*/
//int solve(char* A, char* B) {
//	// write code here
//	int lena = strlen(A);
//	int lenb = strlen(B);
//	if (lena != lenb)
//	{
//		return 0;
//	}
//	char* a = (char*)malloc(sizeof(char)*(lena + lenb + 1));
//	strcat(a, A);
//	strcat(a, A);
//	for (int i = 0; i <= lena; i++)
//	{
//		if (strncmp(a + i, B, lena) == 0)
//		{
//			return 1;
//		}
//	}
//	return 0;
//}







/**给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数
* 进制转换
* @param M int整型 给定整数
* @param N int整型 转换到的进制
* @return string字符串
*/
//char* solve(int M, int N) {
//	// write code here
//	char ch[34] = "\0";
//	int id = 32;
//	int flag = 0;
//	if (M<0)
//	{
//		M = 0 - M;
//		flag = 1;
//	}
//	if (N<10)
//	{
//		while (M)
//		{
//			ch[id--] = (M%N) + '0';
//			M = M / N;
//		}
//	}
//	else
//	{
//		while (M)
//		{
//			if ((M%N)<10)
//			{
//				ch[id--] = (M%N) + '0';
//			}
//			else
//			{
//				ch[id--] = (M%N) - 10 + 'A';
//			}
//			M /= N;
//		}
//	}
//	if (flag == 1)
//	{
//		ch[id--] = '-';
//	}
//	return ch + id + 1;
//}








/**现在有n个物品，每个物品有一个体积v[i]和重量g[i],选择其中总体积恰好为V的若干个物品，想使这若干个物品的总重量最大，求最大总重量为多少。（如果不存在合法方案，返回-1）
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
* @param v int整型一维数组
* @param vLen int v数组长度
* @param g int整型一维数组
* @param gLen int g数组长度
* @param V int整型
* @return int整型
*/
//int Maximumweight(int* v, int vLen, int* g, int gLen, int V) {
//	// write code here
//	int max = -1;
//	for (int i = 0; i<1 << vLen; i++)
//	{
//		int j = 0, sumv = 0, sumg = 0, p = i;
//		while (p>0)
//		{
//			sumv += p % 2 * v[j];
//			sumg += p % 2 * g[j];
//			j++;
//			p /= 2;
//		}
//		if (sumv == V)
//		{
//			max = fmax(max, sumg);
//		}
//	}
//	return max;
//}







/**给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。
* 最大乘积
* @param A int整型一维数组
* @param ALen int A数组长度
* @return long长整型
*/
//long long solve(int* A, int ALen) {
//	// write code here
//	int min1 = 0xfffffff;
//	int min2 = 0xfffffff;
//	int max1 = 0xFfffffff;
//	int max2 = 0xFfffffff;
//	int max3 = 0xFfffffff;
//	for (int i = 0; i<ALen; i++)
//	{
//		int n = A[i];
//		if (n<min1)
//		{
//			min2 = min1;
//			min1 = n;
//		}
//		else if (n<min2)
//		{
//			min2 = n;
//		}
//		if (n>max1)
//		{
//			max3 = max2;
//			max2 = max1;
//			max1 = n;
//		}
//		else if (n>max2)
//		{
//			max3 = max2;
//			max2 = n;
//		}
//		else if (n>max3)
//		{
//			max3 = n;
//		}
//	}
//	return (long)fmax((long)min1*min2*max1, (long)max1*max2*max3);
//}








/**牛牛和牛妹在玩一个取球游戏，有若干个球放置在一个竖直透明的圆柱体中，圆柱体的横截面积恰好与每个球的横截面积相同。这些球只有两种颜色，一种是红色，一种是黑色。
轮到每个人的回合时，每次可以取出其中的两个球，但是需要满足每次取出时只能拿走相邻的两个不同颜色的球。因为这两个球被取出，其他球可能会由于重力的作用而下落。
每次游戏牛牛都是先手，而牛妹是后手。两人交替取球，如果轮到某个人在自己的回合内无法取球，那么判定那个人输。牛牛和牛妹都不想输，所以他们每一步都会采取最优策略。
为了简化该问题，给定你一串由R和B组成的字符串，分别代表红球和黑球，字符串的排列顺序与圆柱体从下往上的排列一致，请你写一个程序，来判定谁会获得胜利，如果牛牛获得胜利，返回"niuniu"，反之，返回"niumei"。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果牛牛获得胜利，返回"niuniu"，反之，返回"niumei"。
* @param s string字符串 一串由R和B组成的字符串，分别代表红球和黑球，字符串的排列顺序与圆柱体从下往上的排列一致
* @return string字符串
*/
//char* getBall(char* s) {
//	// write code here
//	int niu = 0;
//	int mei = 0;
//	int len = strlen(s);
//	for (int i = 0; i<len; i++)
//	{
//		if (s[i] == 'R')
//		{
//			niu++;
//		}
//		else
//		{
//			mei++;
//		}
//	}
//	int min = fmin(mei, niu);
//	if (min % 2 == 0)
//	{
//		return "niumei";
//	}
//	return "niuniu";
//}







//给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。
//
//子数组是数组中的一个连续数字序列。
//
//已知子数组[numsl, numsl + 1, ..., numsr - 1, numsr] ，若对所有 i（l <= i < r），numsi < numsi + 1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/maximum-ascending-subarray-sum
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int maxAscendingSum(int* nums, int numsSize){
//	int max = nums[0];
//	int count = nums[0];
//	for (int i = 0; i<numsSize - 1; i++)
//	{
//		if (nums[i]<nums[i + 1])
//		{
//			count += nums[i + 1];
//			max = fmax(count, max);
//		}
//		else if (nums[i] >= nums[i + 1])
//		{
//			count = 0;
//			count += nums[i + 1];
//			max = fmax(count, max);
//		}
//	}
//	return max;
//}








//当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。
//
//给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/longest-nice-substring
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isok(char* s, int i, int j)
//{
//	int a[26] = { 0 };
//	int b[26] = { 0 };
//	for (int k = i; k <= j; k++)
//	{
//		if (s[k] >= 'a'&&s[k] <= 'z')
//		{
//			a[s[k] - 'a'] = 1;
//		}
//		else
//		{
//			b[s[k] - 'A'] = 1;
//		}
//	}
//	for (int k = 0; k<26; k++)
//	{
//		if (a[k] != b[k])
//		{
//			return false;
//		}
//	}
//	return true;
//}
//char * longestNiceSubstring(char * s){
//	int begin = 0;
//	int len = strlen(s);
//	int len_max = 0;
//	for (int i = 0; i<len; i++)
//	{
//		for (int j = i + 1; j<len; j++)
//		{
//			if (isok(s, i, j) && (j - i + 1)>len_max)
//			{
//				begin = i;
//				len_max = (j - i + 1);
//			}
//		}
//	}
//	char* ret = (char*)calloc(len_max + 1, sizeof(char));
//	for (int i = 0; i<len_max; i++)
//	{
//		ret[i] = s[begin + i];
//	}
//	return ret;
//}








//给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。
//
//交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。
//
//返回使 s 变成 交替字符串 所需的 最少 操作数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/minimum-changes-to-make-alternating-binary-string
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int minOperations(char * s){
//	int zero = 0;
//	int one = 0;
//	int len = strlen(s);
//	for (int i = 0; i<len; i++)
//	{
//		if ((i & 0x01) == 1)
//		{
//			zero += (s[i] == '1');
//			one += (s[i] == '0');
//		}
//		else
//		{
//			zero += (s[i] == '0');
//			one += (s[i] == '1');
//		}
//	}
//	return fmin(zero, one);
//}